﻿#include <iostream>

typedef char TElemType;
#define MaxTreeSize 10

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void InitTree(BiTree &BT) {
    BT = NULL;
}

void CreateTree(BiTree &BT) {
    TElemType e;
    std::cin >> e;
    if (e == '#') {
        e = NULL;
    } else {
        BT = (BiTNode *) malloc(sizeof(BiTNode));
        BT->data = e;
        CreateTree(BT->lchild);
        CreateTree(BT->rchild);
    }
}

void Visit(BiTree BT) {
    std::cout << BT->data;
}


int TreeDepth(BiTree BT) {
    int Lh, Rh;
    if (!BT)
        return 0;
    Lh = TreeDepth(BT->lchild);
    Rh = TreeDepth(BT->rchild);
    return Lh > Rh ? Lh + 1 : Rh + 1;
}

/*
 * 在二叉树中查找值为x的结点，试编写算法打印值为x的结点的所有祖先，假设值为x的结点不多于一个。
 * 操作步骤：后序非递归遍历实现找值为x的所有祖先。
 */
typedef struct {
    BiTree t;
    int tag;
} stack;  // tag=0表示左子女被访问，tag=1表示右子女被访问

void OutputAncestor(BiTree BT, TElemType x) {
    if (!BT) exit(-1);  // 空树，则推出
    BiTNode *stack[MaxTreeSize];
    int top = -1;
    BiTree p = BT, q = NULL;  // p是遍历指针，q指向刚刚访问的结点
    while (p || top > -1) {
        if (p != NULL) {  // 一路向左
            stack[++top] = p;
            p = p->lchild;
        } else {
            p = stack[top];  // 取栈顶元素
            if (p->data == x) {  // 若栈顶元素值为x，则栈中所有元素都是x的祖先
                while (top > -1) {
                    Visit(stack[top--]);
                }
                exit(1);
            }
            if (p->rchild != NULL && p->rchild != q) {
                p = p->rchild;  // 向右走
                stack[++top] = p;
                p = p->lchild;
            } else {  // 否则栈顶元素出栈
                p = stack[top--];
                q = p;   // q指向刚刚访问过的结点
                p = NULL;  // 结点访问完毕后，重置p指针，不然该结点又会重新入栈
            }
        }
    }
}


int main() {
    BiTree BT;
    InitTree(BT);
    std::cout << "请按照先序序列输入树结点创建一棵二叉树（'#'表示空）：\n";
    CreateTree(BT);

    TElemType x;
    std::cout << "请输入要查找的元素值：";
    std::cin >> x;
    std::cout << "该查找元素的所有祖先为：\n";
    OutputAncestor(BT, x);
    return 0;
}